/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package protect02;

import java.math.BigInteger;
import java.util.Random;

/**
 *
 * @author reshetnikovk
 */
public class EuclidExtended {
    
    //МОД(a, b) = d
    //ax + by = d
    
    private static Random rnd = new Random();
    
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ZERO;
    BigInteger d = BigInteger.ZERO;
    BigInteger x = BigInteger.ZERO;
    BigInteger y = BigInteger.ZERO;
    
    /*
        на входе: два неотрицательных числа a и b: a>=b
        на выходе: d=НОД(a,b) и целые x,y: ax + by = d.

        1. Если b=0 положить d:=a, x:=1, y:=0 и возвратить (d,x,y)
        2. Положить x2:=1, x1:=0, y2:=0, y1:=1
        3. Пока b>0
            3.1 q:=[a/b], r:=a-qb, x:=x2-qx1, y:=y2-qy1
            3.2 a:=b, b:=r, x2:=x1, x1:=x, y2:=y1, y1:=y
        4. Положить d:=a, x:=x2, y:=y2 и возвратить (d,x,y)
     */
    
    public static void execute(EuclidExtended params) {
        
        BigInteger a = params.a;
        BigInteger b = params.b;
        BigInteger d; // = params.d;
        BigInteger x; // = params.x;
        BigInteger y; // = params.y;
        
        if (a.compareTo(b) < 0) {
            BigInteger temp = a;
            a = b;
            b = temp;
        }
        
        if (b.equals(BigInteger.ZERO)) {
            d = a;
            x = BigInteger.ONE;
            y = BigInteger.ZERO;
        } else {
            BigInteger q, r;
            BigInteger x1 = BigInteger.ZERO;
            BigInteger x2 = BigInteger.ONE;
            BigInteger y1 = BigInteger.ONE;
            BigInteger y2 = BigInteger.ZERO;
            
            while (b.compareTo(BigInteger.ZERO) > 0) {
                q = a.divide(b);
                r = a.subtract(q.multiply(b));
                
                x = x2.subtract(q.multiply(x1));
                y = y2.subtract(q.multiply(y1));
                
                a = b;
                b = r;
                x2 = x1;
                x1 = x;
                y2 = y1;
                y1 = y;
            }
            
            d = a;
            x = x2;
            y = y2;
        }
          
        /*
        this.d = d;
        this.x = x;
        this.y = y;
        */
        
        //params.a = a;
        //params.b = b;
        
        params.d = d;
        
        params.x = x;
        params.y = y;
        
        //return result;
    }
    
    public static EuclidExtended generateDualPrimary(int length, BigInteger a) {
        
        EuclidExtended params = new EuclidExtended();
        
        params.d = BigInteger.ZERO;
        params.a = a;
        while (!params.d.equals(BigInteger.ONE) || (params.y.compareTo(BigInteger.ZERO) <= 0)) {
            params.b = new BigInteger(length, rnd);
            execute(params);
        }
        
        return params;
    }
}
